Table of contents
Les oracles suivants sont définis:
$$
f_1(x) = x_1^2 + x_2^2 - 2x_1x_2, \nabla f_1 (x) =
\left(
\begin{array}{c}
2 (x_1-x_2)\\
2 (x_2-x_1)
\end{array}
\right)
$$
$$
f_2(x) = 10(x_2 - x_1^2)^2 + (1-x_1)^2, \nabla f_2 (x) =
\left(
\begin{array}{c}
-40 x_1(x_2-x_1^2-2(1x_1)\\
20 (x_2-x_1^2)
\end{array}
\right)
$$
$$
f_3(x) = ||x||_2, \nabla f_3 (x) = \frac{x}{||x||_2}
$$
Gradient descent result - oracle 1 - $x_0=(1,-1)$ - $t=0.5$
The algorithm did not converged in less than 1000 iterations Last gradient :[-4. 4.] Last gradient norm:5.656854249492381 Execution time : 0 secondes
Gradient descent result - oracle 2 - $x_0=(1,-1)$ - $t=0.5$
The algorithm diverged after 3 iterations last gradient:6.432128391102122e+19 The algorithm converged after 3 iterations optimale solution : [1171561. 15039.] minimum : 1.8839076718600384e+25 last gradient:[ 6.43212839e+19 -2.74511032e+13] Execution time : 0 secondes
Gradient descent result - oracle 3 - $x_0=(1,-1)$ - $t=0.5$
The algorithm did not converged in less than 1000 iterations Last gradient :[-0.70710678 0.70710678] Last gradient norm:1.0 Execution time : 0 secondes
Gradient descent result - oracle 3 - $n=10000$ - $t=0.5$
The algorithm did not converged in less than 1000 iterations Last gradient :[0.01 0.01 0.01 ... 0.01 0.01 0.01] Last gradient norm:1.000000000000006 Execution time : 0 secondes
Gradient descent result - oracle 1 - $x_0=(1,-1)$ - $t=0.01$
The algorithm did not converged in less than 100 iterations Last gradient :[ 0.070293 -0.070293] Last gradient norm:0.0994093101618774 Execution time : 0 secondes
Gradient descent result - oracle 2 - $x_0=(1,-1)$ - $t=0.01$
The algorithm converged after 846 iterations optimale solution : [0.98893776 0.97755063] minimum : 0.00012437359560884338 last gradient:[-0.00443146 -0.00894546] Execution time : 0 secondes
Gradient descent result - oracle 3 - $x_0=(1,-1)$ - $t=0.01$
The algorithm did not converged in less than 1000 iterations Last gradient :[ 0.70710678 -0.70710678] Last gradient norm:1.0 Execution time : 0 secondes
Gradient descent result - oracle 1 - $n=10000$ - $t=0.01$
The algorithm did not converged in less than 1000 iterations Last gradient :[0.01 0.01 0.01 ... 0.01 0.01 0.01] Last gradient norm:1.0000000000000075 Execution time : 0 secondes
Armijo gradient descent result - oracle 1 - $x_0=(1,-1)$
L'algorithme de descente de gradient avec Armijo a convergé au bout de 157 itérations solution optimale([ 0.00171519 -0.00171519]) minimum : 1.1767513349899843e-05 dernier gradient:[ 0.00686076 -0.00686076] Temps d'exécution : 0 secondes
Armijo gradient descent result - oracle 2 - $x_0=(1,-1)$
L'algorithme de descente de gradient avec Armijo a convergé au bout de 1056 itérations solution optimale([0.98892624 0.97752737]) minimum : 0.00012463282351631437 dernier gradient:[-0.00443617 -0.00895484] Temps d'exécution : 0 secondes
Armijo gradient descent result - oracle 3 - $x_0=(1,-1)$
L'algorithme de descente de gradient avec Armijo n'a pas convergé en moins de 1000 itérations dernier gradient:[ 0.70710678 -0.70710678] norme dernier gradient:1.0 Temps d'exécution : 0 secondes
Armijo gradient descent result - oracle 4 - $x_0=(10,-10)$
L'algorithme de descente de gradient avec Armijo a convergé au bout de 3827 itérations solution optimale([-0.00498669 0.00016377]) minimum : 2.4926875252853838e-05 dernier gradient:[-0.00997833 0.00065508] Temps d'exécution : 0 secondes
Table of contents $$ \begin{array}{ccc} f_5(x) = ||y-Hx||_2^2, & \nabla f_5(x) = -2 H^{\top}(y-Hx), & \nabla^2f_5(x) = H^{\top}H \end{array} $$ $$ \begin{array}{ccc} min~ f_5(x) & \text{ subject to } ||x||_1\leq \tau & \text{(LASSO)} \end{array} $$ $\mathcal{X} = \{x,||x||_1\leq \tau\}$ is convex because of triangular inequality. $\nabla^2 f_5 > 0$, hence $f_5$ is convex. Therefore (LASSO) problem is convex.
y shape : (255, 1) H shape : (255, 1024)
Given $c\in \mathbb{R}^n$
For all $x\in \mathbb{R}^n$,
$$
c^{\top}x = \sum_{i=1}^n x_ic_i \geq \sum_{i=1}^n -|x_i||c_i| \geq \sum_{i=1}^n -|x_i|\times||c||_{\infty} = - ||x||_1\times||c||_{\infty} \geq - \tau ||c||_{\infty}, \text{ with } ||c||_{\infty} = \underset{i}{max}|c_i|
$$
Note $i^*\in \underset{i}{argmin}|c_i|$, define :
$$
x = \left\{
\begin{array}{cc}
- sign(c_i^*)\tau & \text{ if } i = i^* \\
0 & \text{ if } i\neq i^*
\end{array}
\right.
$$
$$
||x||_1 \leq \tau \text{ and } \forall x'\in \mathbb{R}^n , \text{ s.t } ||x||_1\leq\tau,
$$
$$
c^{\top}x' \geq - \tau ||c||_{\infty} = c^{\top}x
$$
Hence : $ x\in \underset{x'\leq\tau}{\text{ argmin }} c^{\top}x'$
FW algorithm results - oracle 1 - $x_0=(1,-1)$
L'algorithme de descente de gradient avec Armijo a convergé au bout de 81 itérations solution optimale([0.02469136 0. ]) minimum : 0.0006096631611034906 dernier gradient:[ 0.04938272 -0.04938272] Temps d'exécution : 0 secondes
FW algorithm results - oracle 2 - $x_0=(1,-1)$
L'algorithme de descente de gradient avec Armijo a convergé au bout de 338 itérations solution optimale([0.93885602 0.8627184 ]) minimum : 0.007247545902868885 dernier gradient:[ 0.58118617 -0.37464432] Temps d'exécution : 0 secondes
FW algorithm results - oracle 5 - $x_0=0$ - $\tau=20$
L'algorithme de descente de gradient avec Armijo a convergé au bout de 29 itérations solution optimale([0. 0. 0. ... 0. 0. 0.]) minimum : 19.984431079779835 dernier gradient:[-0.26129367 0.54237418 0.02636319 ... -0.09137482 0.66182451 0.08082161] Temps d'exécution : 0 secondes
FW algorithm results - oracle 5 - $x_0=0$ - $\tau=24$
L'algorithme de descente de gradient avec Armijo a convergé au bout de 3728 itérations solution optimale([0. 0. 0. ... 0. 0. 0.]) minimum : 2.0751600203362655 dernier gradient:[-0.10551591 0.10950759 0.03444799 ... 0.02299265 0.25677155 0.05000647] Temps d'exécution : 1 secondes
Result for $\tau = 2$ is saved in X.csv
287.9940335715191
2.0751600203362655